package zhoujian.oj.leetcode;

/**
 * Definition for singly-linked list. 
 * 	public class ListNode { 
 * 		int val; 
 * 		ListNode next; 
 * 		ListNode(int x) { 
 * 			val = x; 
 * 			next = null; 
 * 		} 
 * 	}
 */
public class InsertionSortList {

	public ListNode insertionSortList(ListNode head) {
		if (head == null) {
			return head;
		}
		ListNode inserted = head;

		while (inserted.next != null) {
			ListNode cmp = head;

			if (cmp.val >= inserted.next.val) {
				cmp = inserted.next;
				inserted.next = inserted.next.next;
				cmp.next = head;
				head = cmp;
			} else {
				while (cmp.next.val < inserted.next.val) {
					cmp = cmp.next;
				}
				
				if (cmp != inserted) {
					ListNode tmp = cmp.next;
					cmp.next = inserted.next;
					inserted.next = inserted.next.next;
					cmp.next.next = tmp;
				} else {
					inserted = inserted.next;
				}
			}
		}

		return head;
	}

	public ListNode generateList() {
		ListNode head = new ListNode(5);
		head.next = new ListNode(6);
		head.next.next = new ListNode(3);
		head.next.next.next = new ListNode(4);
		head.next.next.next.next = new ListNode(1);
		return head;
	}

	public void printList(ListNode head) {
		while (head != null) {
			System.out.print(head.val + " ");
			head = head.next;
		}
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		InsertionSortList isl = new InsertionSortList();
		isl.printList(isl.insertionSortList(isl.generateList()));

	}

}
